package com.breeze.leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * https://leetcode-cn.com/problems/triangle/
 * 120. 三角形最小路径和
 * 给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。
 * <p>
 * 相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。
 */
public class LeetCode120 {
    /**
     * 方法1： 动态规划
     * -> dp二维数组用来表示用来表示对应三角形位置的最小路径和,c表示对应三角形位置的值
     * ->状态转移方程：
     * dp[i][j] = min(dp[i-1][j-1],dp[i-1][j]) + c[i][j]
     * dp[i][j] = dp[i-1][j-1], (j=i)
     * dp[i][0] = dp[i-1][0] + c[i][0], (j=0)
     * dp[0][0] = c[0][0],(i=0,j=0)
     * <p>
     * 时间复杂度：O(n^2)
     * 空间复杂度：O(n^2)
     */
    public int minimumTotal(List<List<Integer>> triangle) {
        int n = triangle.size();
        int[][] dp = new int[n][n];
        for (int i = 0; i < n; i++) {
            List<Integer> items = triangle.get(i);
            for (int j = 0; j < items.size(); j++) {
                if (i == 0 && j == 0) {
                    dp[0][0] = items.get(j);
                } else if (j == 0) {
                    dp[i][0] = dp[i - 1][0] + items.get(0);
                } else if (j == i) {
                    dp[i][j] = dp[i - 1][j - 1] + items.get(j);
                } else {
                    dp[i][j] = Math.min(dp[i - 1][j - 1], dp[i - 1][j]) + items.get(j);
                }
            }
        }

        int minimum = Integer.MAX_VALUE;
        for (int value : dp[n - 1]) {
            minimum = Math.min(minimum, value);
        }
        return minimum;
    }

    /**
     * 方法1：动态规划小优化
     * 其实也算不上优化，只是减少了几次条件判断
     */
    public int minimumTotal1(List<List<Integer>> triangle) {
        int n = triangle.size();
        int[][] dp = new int[n][n];
        dp[0][0] = triangle.get(0).get(0);
        for (int i = 1; i < n; i++) {
            dp[i][0] = dp[i - 1][0] + triangle.get(i).get(0);
            for (int j = 1; j < i; j++) {
                dp[i][j] = Math.min(dp[i - 1][j - 1], dp[i - 1][j]) + triangle.get(i).get(j);
            }
            dp[i][i] = dp[i - 1][i - 1] + triangle.get(i).get(i);
        }

        int minimum = dp[n - 1][0];
        for (int i = 1; i < n; i++) {
            minimum = Math.min(minimum, dp[n - 1][i]);
        }
        return minimum;
    }

    /**
     * 方法2：动态规划
     * 说明：
     * 如果你可以只使用 O(n) 的额外空间（n 为三角形的总行数）来解决这个问题，那么你的算法会很加分。
     */
    public int minimumTotal2(List<List<Integer>> triangle) {
        int n = triangle.size();
        int[] dp = new int[n];
        dp[0] = triangle.get(0).get(0);
        for (int i = 1; i < n; i++) {
            int pre1 = dp[0], pre2 = dp[1];
            dp[0] = pre1 + triangle.get(i).get(0);
            for (int j = 1; j < i; j++) {
                dp[j] = Math.min(pre1, pre2) + triangle.get(i).get(j);
                pre1 = pre2;
                if (j < i - 1) {
                    pre2 = dp[j + 1];
                }
            }
            dp[i] = pre1 + triangle.get(i).get(i);
        }

        int minimum = dp[0];
        for (int i = 1; i < n; i++) {
            minimum = Math.min(minimum, dp[i]);
        }
        return minimum;
    }


    /**
     * // TODO:最强代码
     * https://leetcode-cn.com/problems/triangle/solution/di-gui-ji-yi-hua-dp-bi-xu-miao-dong-by-sweetiee/
     */

    public static void main(String[] args) {

        List<List<Integer>> triangle = new ArrayList<>();
        triangle.add(Arrays.asList(2));
        triangle.add(Arrays.asList(3, 4));
        triangle.add(Arrays.asList(6, 5, 7));
        triangle.add(Arrays.asList(4, 1, 8, 3));
        LeetCode120 leetCode120 = new LeetCode120();
        System.out.println(leetCode120.minimumTotal2(triangle));
    }
}
